from typing import List


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        len_strs = len(strs)
        if len_strs == 0:
            return ""
        return self.divideAndConquer(strs, 0, len_strs - 1)

    def divideAndConquer(self, strs: List[str], left: int, right: int) -> str:
        if left == right:
            return strs[left]
        else:
            mid = (left + right) // 2
            new_left = self.divideAndConquer(strs, left, mid)
            new_right = self.divideAndConquer(strs, mid + 1, right)
            return self.findCommonPrefix(new_left, new_right)

    def findCommonPrefix(self, a: str, b: str) -> str:
        min_length = min(len(a), len(b))
        for i in range(min_length):
            if a[i] != b[i]:
                return a[0:i]
        return a[0:min_length]
